Localization is the process of determining or marking the location of objects or places of interest within a physical environment in two or three dimensions. Frequently, the environment is uncharted, remote, or inaccessible to conventional measuring techniques. Knowing the locations of objects or places can assist navigation or object retrieval or placement. For example, in a search and rescue scenario, the locations of victims or hazardous conditions should first be established to protect rescue personnel who must enter a disaster area.
Locations are marked relative to a stationary point of reference located either within or outside of the environment. Performing localization based on an external point of reference, such as through Global Positioning System (GPS) spatial coordinates, is trivial. Nevertheless, the external reference points must be accessible from each location within the environment, which can be infeasible if the external reference points are obstructed or are otherwise unavailable, such as occurs, for instance, indoors or underground, where GPS signals are blocked.
Performing localization relative to multiple distributed reference points within the environment can avoid the shortcomings of external reference points. To determine the relative location of a new point, the positions of known local reference points are measured and evaluated to form a location estimate. Distributed localization, though, is susceptible to noise, which can cause ranging errors in position and distance. Distributed localization is particularly difficult if the terrain of the environment is unpredictable or unknown and unexpected obstructions interfere with or decrease the accuracy of local reference points. Moreover, ranging errors have a tendency to propagate and be amplified through successive measurements. Several forms of distributed localization exist.
Multi-dimensional scaling (MDS) is one form of distributed localization that transforms proximity data into a geometric embedding, such as described in Y. Sheng et al., “Localization From Connectivity in Sensor Networks,” IEEE Trans. on Para. and Distr. Sys., V. 15 (10) (October 2004), the disclosure of which is incorporated by reference. MDS-based localization computes the shortest path distance between all pairs of nodes, applies multi-dimensional scaling to a distance matrix, and transforms a relative map into an absolute map using known positions of anchor nodes. While MDS-based localization has a high success rate for connected networks, errors can be large if the network has high dilation.
Semidefinite programming (SDP) is another form of distributed localization that transforms a minimization problem into a semidefinite programming problem, such as described in P. Biswas, “Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization,” ACM/Conf. Info. Proc. in Sensor Nets. (2004), the disclosure of which is incorporated by reference. The environment must exhibit a uniquely localizability property. However, the property will not be satisfied if the network has fewer anchor nodes or connections than necessary or the ranging data exhibits large noise errors.
The incremental least squares (ILS) algorithm is yet another form of distributed localization that uses an error registry to choose neighboring nodes with locations favorable in terms of noise and error propagation model, such as described in F. Zhao, “Incremental Node Localization With Error Propagation Control In Ad Hoc Networks,” Tech. Report P200310265, Xerox PARC (2004), the disclosure of which is incorporated by reference. The propagation model is used to generate a self-location estimate using multilateration. However, the approach requires at least s+1 known neighboring locations, where s is 2 or 3, and sufficient knowledge of error characteristics to enable the localization estimation to converge over successive iterations.
The shortest path approximation (SPA) is a form of distributed localization that computes the shortest paths from any node to anchor nodes and uses the path distances to approximate Euclidean distances, such described in K. Whitehouse, “Calamari: a Localization System For Sensor Networks,” available at http://www.cs.berkley.edu/kamin/calamari (2003), the disclosure of which is incorporated by reference. The unknown node locations are computed using multilateration, given anchor node distances. However, SPA-based localization introduces large errors if the network exhibits high dilation or low connectivity.
Therefore, there is a need for an approach to determining the relative position of objects or places within an environment without reliance on pre-existing fixed points of reference. Preferably, such an approach would be able to decrease ranging error propagation by dynamically deploying points of reference within the environment while minimizing any resulting error conditions.